/*
* 随机生成 1-100 20个数
* */

// [0,1)
function getRandom(min, max, count) {
  // 循环几次 count次
  let arr = [];
  for (let i = 0; i < count; i++) {
    arr.push(Math.floor(Math.random() * (max - min + 1) + min));
  }
  return arr;
}

/*
* 冒泡排序
* 两杯水  3L  5L  调换一下
* 空的杯子
* */
let count1 = 0;

/*冒泡排序*/
function bSort(arr) { // len^2 O(n^2)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        count1++;
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

let count2 = 0;

/*选择排序*/
function xSort(arr) { // 时间复杂度 O(N^2)

  // 1. 先取出最小值的下标
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        count2++;
        minIndex = j;
      }
    }
    [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
  }
  return arr;
}

let count3 = 0;

/*插入排序*/
function iSort(arr) {
  const len = arr.length;
  let preIndex;
  for (let i = 1; i < len; i++) {
    // 记录排好序的插入的下标
    preIndex = i - 1;
    let aa = arr[i];
    /*循环的次数 确定 for  不确定 while*/
    while (preIndex >= 0 && arr[preIndex] > aa) {
      // 记录的下标 对应的值 > 要插入的值
      // 记录的值 要向后移动
      count3++;
      arr[preIndex + 1] = arr[preIndex];
      // 记录的值 的下标 要向前移动一位
      preIndex -= 1;
    }
    arr[preIndex + 1] = aa;
  }
  return arr;
}

let count4 = 0;

/*快速排序*/
function qSort(arr) {
  // 1. 两个空间
  // 左  右
  if (arr.length <= 1) return arr;
  const left = [];
  const right = [];
  let mid = arr[0];
  for (let i = 1; i < arr.length; i++) {
    // 开始判断 谁放到左边 谁放到右边
    count4++;
    if (mid > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return ([...qSort(left), mid, ...qSort(right)]);
}

let count5 = 0;
function gSort(arr) {
  // 1. 找到中间的位置
  count5++;
  let len = arr.length;
  if (len <= 1) return arr;
  let middle = Math.floor(len / 2);
  // 2. 分成两部分
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  // 继续分
  // left 排好序 右边也要排好序
  return merge(gSort(left), gSort(right));
}

function merge(left, right) {
  // 排序之后的数组 left 和 right : 合并
  let result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;

}

let max = 1000000000;
let count = 100000000;

// let randomArr1 = getRandom(1, max, count);
// console.log(randomArr);
//
// let startTime = new Date() - 0;
// bSort(randomArr1);
// let endTime = new Date() - 0;
// console.log('冒泡排序用时', endTime - startTime, 'ms', '次数:', count1);
//
// let randomArr2 = getRandom(1, max, count);
// startTime = new Date() - 0;
// let res = xSort(randomArr2);
// // console.log(res);
// endTime = new Date() - 0;
// console.log('选择排序用时', endTime - startTime, 'ms', '次数:', count2);
//
// let randomArr3 = getRandom(1, max, count);
// startTime = new Date() - 0;
// res = iSort(randomArr3);
// // console.log(res);
// endTime = new Date() - 0;
// console.log('插入排序用时', endTime - startTime, 'ms', '次数:', count3);

let randomArr4 = getRandom(1, max, count);
startTime = new Date() - 0;
res = qSort(randomArr4);
// console.log(res);
endTime = new Date() - 0;
console.log('快速排序用时', endTime - startTime, 'ms', '次数:', count4);
//
// let randomArr5 = getRandom(1, max, count);
// startTime = new Date() - 0;
// res = gSort(randomArr5);
// // console.log(res);
// endTime = new Date() - 0;
// console.log('归并排序用时', endTime - startTime, 'ms', '次数:', count5);


//快速排序用时 25 ms 次数: 72073
//插入排序用时 33 ms 次数: 6196550
//选择排序用时 53 ms 次数: 35225
//冒泡排序用时 53 ms 次数: 6323110
